package org.example.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;

public class Test {

    public static void main(String[] args) {
        System.out.println(evalRPN(new String[]{"4","13","5","/","+"}));
    }

    /**
     * 20.有效的括号
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     * 示例 1：
     * 输入：s = "()"
     * 输出：true
     * 示例 2：
     * 输入：s = "()[]{}"
     * 输出：true
     * 示例 3：
     * 输入：s = "(]"
     * 输出：false
     * 思路：：
     * 如果是 (，{，[，则直接放入栈中。
     * 如果是),],}，此时如果已是空 或者 stack pop出来的元素与当前字符匹配不上，则return false
     */
    public static boolean isValid(String s) {
        if (s.length() == 0) return false;
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (stack.isEmpty() || !judge(stack.peek(), c)) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static boolean judge(Character sc, Character c) {
        switch (c) {
            case ')':
                return sc == '(';
            case ']':
                return sc == '[';
            case '}':
                return sc == '{';
            default:
                return false;
        }
    }

    /**
     * 71.简化路径：
     * 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
     * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；
     * 两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。
     * 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
     * 请注意，返回的 规范路径 必须遵循下述格式：
     * 始终以斜杠 '/' 开头。
     * 两个目录名之间必须只有一个斜杠 '/' 。
     * 最后一个目录名（如果存在）不能 以 '/' 结尾。
     * 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
     * 返回简化后得到的 规范路径 。
     * 第一种方法：API 用 java.nio.file.Path. 直接用Path.of(String str).normalize().toString();
     * 第二种方法：用栈。因为多个//会变成/，且各种names都用/分割，所以一开始直接用将names分割
     * 最后感觉是用的队列的思想，一开始我需要用栈的思想，把name先压进去，最后还原的时候，要让先进先出。
     */
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new LinkedList<>();
        for(String name : names){
            if("..".equals(name)){
                if(!stack.isEmpty()){
                    stack.pop();
                }
            }else if(name.length() > 0 && !".".equals(name)){
                stack.push(name);
            }
        }
        StringBuilder sb = new StringBuilder();
        if(stack.isEmpty()){
            sb.append("/");
            return sb.toString();
        }
        while(!stack.isEmpty()){
            sb.append("/");
            sb.append(stack.pollFirst());
        }
        return path;
        //        return Path.of(path).normalize().toString();
    }

    /**
     * 150：leetcode：逆波兰表达式
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * 注意：
     * 有效的算符为 '+'、'-'、'*' 和 '/' 。
     * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
     * 两个整数之间的除法总是 向零截断 。
     * 表达式中不含除零运算。
     * 输入是一个根据逆波兰表示法表示的算术表达式。
     * 答案及所有中间计算结果可以用 32 位 整数表示。
     *
     * 思路：
     * 逆波兰表达式：
     * 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
     * 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
     * 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
     * 逆波兰表达式主要有以下两个优点：
     * 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
     * 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
     */
    public static int evalRPN(String[] tokens) {
        Deque<String> stack = new LinkedList<>();
        for(String str : tokens){
            switch (str){
                case "+":
                case "-":
                case "*":
                case "/":
                    String m = stack.pop();
                    String n = stack.pop();
                    stack.push(calculate(str, n, m));
                    break;
                default:
                    stack.push(str);
                    break;
            }
        }
        return Integer.parseInt(stack.pop());
    }

    private static String calculate(String str, String n, String m) {
        switch (str){
            case "+":
                return String.valueOf(Integer.parseInt(n) + Integer.parseInt(m));
            case "-":
                return String.valueOf(Integer.parseInt(n) - Integer.parseInt(m));
            case "*":
                return String.valueOf(Integer.parseInt(n) * Integer.parseInt(m));
            case "/":
                return String.valueOf(Integer.parseInt(n) / Integer.parseInt(m));
            default:
                return str;
        }
    }

    /**
     * 栈第224题，基本计算器。
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     * 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
     * 示例 1：
     * 输入：s = "1 + 1"
     * 输出：2
     * 示例 2：
     * 输入：s = " 2-1 + 2 "
     * 输出：3
     * 示例 3：
     * 输入：s = "(1+(4+5+2)-3)+(6+8)"
     * 输出：23
     *
     * 思路：
     * 第一个是 ： 括号展开+栈+变量反转
     * 第二个是 ： 双栈解决问题。第一个栈放所有的数字，第二个栈放除了数字以外任何操作
     * ops栈，遇到(，直接将对应的(放到栈中，等待)。
     * )使用现有的nums和ops直接计算，直到没有操作，或者遇到了左括号
     */
    public int calculate(String s) {
        Deque<Integer> number = new LinkedList<>();
        number.offerFirst(0);
        s = s.replaceAll(" ", "");
        Deque<Character> operations = new LinkedList<>();
        char[] cs = s.toCharArray();
        int n = cs.length;
        for(int i = 0; i < n; i++){
            char c = cs[i];
            if(c == '('){
                operations.offerFirst(c);
            } else if (c == ')') {
                while(!operations.isEmpty()){
                    char cc = operations.peekFirst();
                    if(cc != '('){
                        calc(number, operations);
                    }else{
                        operations.pollFirst();
                        break;
                    }
                }
            }else{
                if(Character.isDigit(c)){
                    int u = 0;
                    int j = i;
                    while(j < n && Character.isDigit(cs[j])){
                        u = u * 10 + cs[j++] - '0';
                    }
                    number.offerFirst(u);
                    i = j - 1;
                }else{
                    if(i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')){
                        number.offerFirst(0);
                    }
                    while(!operations.isEmpty() && operations.peekFirst() != '(') calc(number, operations);
                    operations.offerFirst(c);
                }
            }
        }
        while(!operations.isEmpty()) calc(number, operations);
        return number.peekFirst();
    }

    private void calc(Deque<Integer> number, Deque<Character> operations) {
        if(Objects.isNull(number) || number.size() < 2) return;
        if(operations.isEmpty()) return;
        int b = number.pollFirst(), a = number.pollFirst();
        char op = operations.pollFirst();
        number.offerFirst(op == '+' ? a + b : a - b);
    }
}
